package com.zm.demo.core.sort;

import java.util.Arrays;
import java.util.Random;

import static java.lang.System.out;

/**
 * @author zoum
 * @create 2020/3/10 13:17
 */
public class MergeSort2 {

    private static Random random = new Random();

    public static void main(String[] args){
        int[] s = new int[10];
        for (int i = 0; i < s.length; i++) {
            s[i] = new Random().nextInt(1000);
        }


        out.println(Arrays.toString(s));
        out.println(s.length);
        int[]r = mergeSort(s, 0, s.length-1);
        out.println(Arrays.toString(r));

    }

    public static int[] mergeSort(int[] source, int start, int end) {
        if (start==end){
            return new int[]{source[start]};
        }else if (start > end){
            return null;
        }

        int mid = (start+end)/2;
        if (mid == start){
            return merge(new int[]{source[mid]}, mergeSort(source, mid+1, end));
        }else {
            return merge(mergeSort(source, start, mid), mergeSort(source, mid+1,end));
        }
    }

    public static int[] merge(int []sort1, int []sort2){
        if (sort1 == null){
            return sort2;
        }
        if (sort2 == null){
            return sort1;
        }

        int[]r = new int[sort1.length+sort2.length];
        int k=0;
        for (int i = 0, j=0;  ; ) {
            if (i>=sort1.length && j>=sort2.length){
                break;
            }
            if (i>=sort1.length){
                r[k++] = sort2[j++];
            }else if (j>=sort2.length){
                r[k++] = sort1[i++];
            }else {
                if (sort1[i]<sort2[j]){
                    r[k++] = sort1[i++];
                }else {
                    r[k++] = sort2[j++];
                }
            }
        }
        return r;
    }
}
